class Quadtree {
    constructor(bounds, maxDepth = 4, maxObjects = 4, depth = 0) {
        this.bounds = bounds; // {x, y, width, height}
        this.maxDepth = maxDepth;
        this.maxObjects = maxObjects;
        this.depth = depth;
        this.objects = [];
        this.nodes = [];
    }

    // 获取物体对应的边界框
    static getBounds(obj) {
        if (obj.type === 'rect') {
            // 计算旋转后矩形的边界框
            const cosAngle = Math.cos(obj.rotation);
            const sinAngle = Math.sin(obj.rotation);
            const w = obj.width;
            const h = obj.height;
            const rotatedWidth = Math.abs(w * cosAngle) + Math.abs(h * sinAngle);
            const rotatedHeight = Math.abs(w * sinAngle) + Math.abs(h * cosAngle);
            return {
                x: obj.x - rotatedWidth / 2,
                y: obj.y - rotatedHeight / 2,
                width: rotatedWidth,
                height: rotatedHeight
            };
        }
        return { // 圆形转换为AABB
            x: obj.x - obj.radius,
            y: obj.y - obj.radius,
            width: obj.radius * 2,
            height: obj.radius * 2
        };
    }

    // 分裂为四个子节点
    split() {
        const nextDepth = this.depth + 1;
        const { x, y, width, height } = this.bounds;
        const subWidth = width / 2;
        const subHeight = height / 2;

        this.nodes = [
            new Quadtree({ x: x, y: y, width: subWidth, height: subHeight },
                this.maxDepth, this.maxObjects, nextDepth),
            new Quadtree({ x: x + subWidth, y: y, width: subWidth, height: subHeight },
                this.maxDepth, this.maxObjects, nextDepth),
            new Quadtree({ x: x, y: y + subHeight, width: subWidth, height: subHeight },
                this.maxDepth, this.maxObjects, nextDepth),
            new Quadtree({ x: x + subWidth, y: y + subHeight, width: subWidth, height: subHeight },
                this.maxDepth, this.maxObjects, nextDepth)
        ];
    }

    // 插入对象到四叉树
    insert(obj) {
        if (this.nodes.length) {
            const index = this.getIndex(obj);
            if (index !== -1) {
                this.nodes[index].insert(obj);
                return;
            }
        }

        this.objects.push(obj);

        if (this.objects.length > this.maxObjects &&
            this.depth < this.maxDepth &&
            !this.nodes.length) {
            this.split();
            for (let i = 0; i < this.objects.length;) {
                const index = this.getIndex(this.objects[i]);
                if (index !== -1) {
                    this.nodes[index].insert(this.objects.splice(i, 1)[0]);
                } else {
                    i++;
                }
            }
        }
    }

    // 获取物体所属的子节点索引
    getIndex(obj) {
        const bounds = Quadtree.getBounds(obj);
        const verticalMid = this.bounds.x + this.bounds.width / 2;
        const horizontalMid = this.bounds.y + this.bounds.height / 2;

        const top = bounds.y < horizontalMid &&
            bounds.y + bounds.height < horizontalMid;
        const bottom = bounds.y > horizontalMid;
        const left = bounds.x < verticalMid &&
            bounds.x + bounds.width < verticalMid;
        const right = bounds.x > verticalMid;

        if (top) {
            if (left) return 0;
            if (right) return 1;
        } else if (bottom) {
            if (left) return 2;
            if (right) return 3;
        }
        return -1; // 跨多个区域
    }

    // 查询可能碰撞的对象
    retrieve(obj) {
        let returnObjects = this.objects.slice();
        if (this.nodes.length) {
            const index = this.getIndex(obj);
            if (index !== -1) {
                returnObjects = returnObjects.concat(
                    this.nodes[index].retrieve(obj));
            } else {
                for (const node of this.nodes) {
                    returnObjects = returnObjects.concat(node.retrieve(obj));
                }
            }
        }
        return returnObjects;
    }

    // 碰撞检测入口
    static detectCollisions(objects) {
        const bounds = objects.reduce((acc, obj) => {
            const b = Quadtree.getBounds(obj);
            return {
                xMin: Math.min(acc.xMin, b.x),
                yMin: Math.min(acc.yMin, b.y),
                xMax: Math.max(acc.xMax, b.x + b.width),
                yMax: Math.max(acc.yMax, b.y + b.height)
            };
        }, { xMin: Infinity, yMin: Infinity, xMax: -Infinity, yMax: -Infinity });

        const qt = new Quadtree({
            x: bounds.xMin,
            y: bounds.yMin,
            width: bounds.xMax - bounds.xMin,
            height: bounds.yMax - bounds.yMin
        });

        const collisions = [];
        for (const obj of objects) {
            const candidates = qt.retrieve(obj);
            for (const candidate of candidates) {
                // 只处理怪物和子弹之间的碰撞
                if ((obj.groupId === 1 && candidate.groupId === 2) || 
                    (obj.groupId === 2 && candidate.groupId === 1)) {
                    if (this.checkCollision(obj, candidate)) {
                        collisions.push([obj, candidate]);
                    }
                }
            }
            qt.insert(obj);
        }
        return collisions;
    }

    // 获取矩形的顶点
    static getRectVertices(rect) {
        const cosAngle = Math.cos(rect.rotation);
        const sinAngle = Math.sin(rect.rotation);
        const halfWidth = rect.width / 2;
        const halfHeight = rect.height / 2;
        const vertices = [];
        const points = [
            [-halfWidth, -halfHeight],
            [halfWidth, -halfHeight],
            [halfWidth, halfHeight],
            [-halfWidth, halfHeight]
        ];
        for (const [px, py] of points) {
            const rotatedX = rect.x + px * cosAngle - py * sinAngle;
            const rotatedY = rect.y + px * sinAngle + py * cosAngle;
            vertices.push([rotatedX, rotatedY]);
        }
        return vertices;
    }

    // 获取多边形的所有投影轴
    static getAxes(vertices) {
        const axes = [];
        for (let i = 0; i < vertices.length; i++) {
            const p1 = vertices[i];
            const p2 = vertices[(i + 1) % vertices.length];
            const edge = [p2[0] - p1[0], p2[1] - p1[1]];
            const normal = [-edge[1], edge[0]];
            axes.push(normal);
        }
        return axes;
    }

    // 将多边形投影到轴上
    static project(vertices, axis) {
        let min = Infinity;
        let max = -Infinity;
        for (const vertex of vertices) {
            const dotProduct = vertex[0] * axis[0] + vertex[1] * axis[1];
            min = Math.min(min, dotProduct);
            max = Math.max(max, dotProduct);
        }
        return { min, max };
    }

    // 检查两个投影是否重叠
    static overlap(proj1, proj2) {
        return !(proj1.max < proj2.min || proj2.max < proj1.min);
    }

    // 碰撞检测核心逻辑
    static checkCollision(a, b) {
        // 矩形 vs 矩形
        if (a.type === 'rect' && b.type === 'rect') {
            const verticesA = this.getRectVertices(a);
            const verticesB = this.getRectVertices(b);
            const axesA = this.getAxes(verticesA);
            const axesB = this.getAxes(verticesB);
            const allAxes = axesA.concat(axesB);

            for (const axis of allAxes) {
                const projA = this.project(verticesA, axis);
                const projB = this.project(verticesB, axis);
                if (!this.overlap(projA, projB)) {
                    return false;
                }
            }
            return true;
        }

        // 圆形 vs 圆形
        if (a.type === 'circle' && b.type === 'circle') {
            const dx = a.x - b.x;
            const dy = a.y - b.y;
            const distance = Math.sqrt(dx * dx + dy * dy);
            return distance < a.radius + b.radius;
        }

        // 矩形 vs 圆形
        const rect = a.type === 'rect' ? a : b;
        const circle = a.type === 'circle' ? a : b;
        const vertices = this.getRectVertices(rect);
        const axes = this.getAxes(vertices);
        const circleCenter = [circle.x, circle.y];

        for (const axis of axes) {
            const projRect = this.project(vertices, axis);
            const projCircle = {
                min: circleCenter[0] * axis[0] + circleCenter[1] * axis[1] - circle.radius,
                max: circleCenter[0] * axis[0] + circleCenter[1] * axis[1] + circle.radius
            };
            if (!this.overlap(projRect, projCircle)) {
                return false;
            }
        }

        // 额外检查圆心到矩形边的距离
        for (let i = 0; i < vertices.length; i++) {
            const p1 = vertices[i];
            const p2 = vertices[(i + 1) % vertices.length];
            const edge = [p2[0] - p1[0], p2[1] - p1[1]];
            const normal = [-edge[1], edge[0]];
            const centerToP1 = [circle.x - p1[0], circle.y - p1[1]];
            const dot = centerToP1[0] * normal[0] + centerToP1[1] * normal[1];
            if (Math.abs(dot) < circle.radius) {
                return true;
            }
        }

        return false;
    }
}

// 动态更新位置的方法
class GameObject {
    constructor({ id, type, x, y, width, height, rotation = 0, radius = 0, groupId }) {
        this.id = id;
        this.type = type;
        this.x = x;
        this.y = y;
        this.width = width;
        this.height = height;
        this.rotation = rotation;
        this.radius = radius;
        this.groupId = groupId;
    }

    // 更新位置并重新插入四叉树
    updatePosition(x, y, quadtree) {
        // 从四叉树中删除
        quadtree.objects = quadtree.objects.filter(obj => obj.id !== this.id);

        // 更新位置
        this.x = x;
        this.y = y;

        // 重新插入
        quadtree.insert(this);
    }
}

// 使用示例
const objects = [
    new GameObject({ id: 1, type: 'rect', x: 0, y: 0, width: 100, height: 50, groupId: 1 }),
    new GameObject({ id: 2, type: 'rect', x: 80, y: 51, width: 100, height: 50, rotation: -3, groupId: 2 }),
    new GameObject({ id: 3, type: 'rect', x: 80, y: 51, width: 100, height: 50, rotation: -3, groupId: 2 }),
    new GameObject({ id: 4, type: 'rect', x: 80, y: 51, width: 100, height: 50, rotation: -3, groupId: 2 }),
    new GameObject({ id: 5, type: 'rect', x: 80, y: 51, width: 100, height: 50, rotation: -3, groupId: 2 }),
];

// const qt = new Quadtree({ x: 0, y: 0, width: 400, height: 400 });

// objects.forEach(obj => qt.insert(obj));

// // 假设物体 1 和 2 更新位置
// objects[0].updatePosition(150, 150, qt);
// objects[1].updatePosition(200, 200, qt);

// 检查碰撞
const collisions = Quadtree.detectCollisions(objects);
console.log('碰撞对:', collisions);